package MyPriorityQueue;

import java.util.*;

/**
 * 1497. 检查数组对是否可以被 k 整除
 * <p>
 * 给你一个整数数组 arr 和一个整数 k ，其中数组长度是偶数，值为 n 。
 * <p>
 * 现在需要把数组恰好分成 n / 2 对，以使每对数字的和都能够被 k 整除。
 * <p>
 * 如果存在这样的分法，请返回 True ；否则，返回 False 。
 */
public class Leetcode1497 {
    public static boolean canArrange(int[] arr, int k) {
        int len = arr.length;
        // 奇数个直接排除
        if (len % 2 != 0) {
            return false;
        }
        Map<Integer, Integer> mp = new HashMap<Integer, Integer>();
        for (int num : arr) {
            //计算余数及map中该值的个数
            int mod = ((num % k) + k) % k;
            int current = mp.getOrDefault(mod, 0);
            mp.put(mod, current + 1);
        }
        System.out.println(mp.toString());

        Iterator<Map.Entry<Integer, Integer>> it = mp.entrySet().iterator();

        int count = len / 2;
        while (it.hasNext() && count > 0) {
            Map.Entry<Integer, Integer> entry = it.next();
            int key = entry.getKey();
            int mod = entry.getValue();

            int reverse_key_num = mp.getOrDefault((k - key) % k, 0);
            // 这里的0需要进行特殊处理
            // [0,0,0,4] 8 测试用例
            if (key == 0) {
                if (reverse_key_num % 2 != 0) {
                    return false;
                }
                count -= reverse_key_num / 2;
            }else{
                if (reverse_key_num != mod || reverse_key_num == 0) {
                    return false;
                }
                count -= reverse_key_num;
            }
        }
        return true;
    }


    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 3, 4, 5, 10, 6, 7, 8, 9};
        System.out.println(canArrange(arr, 5));

    }
}
